﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;

namespace CSharpAlgorithm
{
    class MakeOnionSnack
    {
        public MakeOnionSnack()
        {
            int boardSize = GetConsole.GetInt();
            int cutCount = GetConsole.GetInt();
            int[,] board = new int[boardSize, boardSize];
            //입력
            for (int x = 0; x < boardSize; x++)
            {
                for (int y = 0; y < boardSize; y++)
                {
                    board[x, y] = GetConsole.GetInt();
                }
            }
            List<OnionSnack> snackList = new List<OnionSnack>();
            //처리
            for (int x1 = 0; x1 < boardSize - 3; x1++)
            {
                for (int y1 = 0; y1 < boardSize - 3; y1++)
                {
                    int[,] xSumBoard = new int[boardSize, boardSize]; //x 방향으로 누적
                    int[,] ySumBoard = new int[boardSize, boardSize]; //y 방향으로 누적
                    xSumBoard[x1, y1] = board[x1, y1];
                    ySumBoard[x1, y1] = board[x1, y1];
                    for (int i = x1 + 1; i < boardSize; i++)
                    {
                        xSumBoard[i, y1] = board[i, y1] + xSumBoard[i - 1, y1];
                        ySumBoard[i, y1] = board[i, y1];
                    }
                    for (int i = y1 + 1; i < boardSize; i++)
                    {
                        ySumBoard[x1, i] = board[x1, i] + ySumBoard[x1, i - 1];
                        xSumBoard[x1, i] = board[x1, i];
                    }
                    for (int x2 = x1 + 1; x2 < boardSize; x2++)
                    {
                        for (int y2 = y1 + 1; y2 < boardSize; y2++)
                        {
                            xSumBoard[x2, y2] = board[x2, y2] + xSumBoard[x2 - 1, y2];
                            ySumBoard[x2, y2] = board[x2, y2] + ySumBoard[x2, y2 - 1];
                            if (x2 > x1 + 1 && y2 > y1 + 1)
                            {
                                int taste = xSumBoard[x2, y1] + xSumBoard[x2, y2] + ySumBoard[x1, y2] + ySumBoard[x2, y2] - board[x1, y1] - board[x1, y2] - board[x2, y1] - board[x2, y2];
                                OnionSnack snack = new OnionSnack(x1, y1, x2, y2, taste);
                                snackList.Add(snack);
                            }
                        }
                    }
                }
            }

            //출력
            string result = string.Empty;
            for (int i = 0; i < cutCount; i++)
            {
                if (snackList.Count == 0)
                {
                    result = "0\n";
                    break;
                }
                int bestTaste = snackList.Max(s => s.Taste);
                OnionSnack bestSnack = snackList.Find(s => s.Taste == bestTaste);
                result += bestSnack.Taste + " " + (bestSnack.X1 + 1) + " " + (bestSnack.Y1 + 1) + " " + (bestSnack.X2 + 1) + " " + (bestSnack.Y2 + 1) + "\n";
                snackList.RemoveAll(s => !CheckCrossBox(s, bestSnack));
                snackList.Remove(bestSnack);
            }
            Console.WriteLine(result);

        }
        private bool CheckCrossBox(OnionSnack snack, OnionSnack bestSnack)
        {
            if (snack.X1 > bestSnack.X1 
                && snack.X2 < bestSnack.X2
                && snack.Y1 > bestSnack.Y1
                && snack.Y2 < bestSnack.Y2) //박스가 안에 들어가는지
                {
                    return true;
                }
            if (snack.Y2 < bestSnack.Y1 //박스가 바깥쪽에 있는지
                || snack.X2 < bestSnack.X1
                || snack.X1 > bestSnack.X2
                || snack.Y1 > bestSnack.X2)
                {
                    return true;
                }
            return false;
        }
    }
    struct OnionSnack
    {
        private int x1, y1, x2, y2, taste;
        public int X1 { get { return x1; } }
        public int Y1 { get { return y1; } }
        public int X2 { get { return x2; } }
        public int Y2 { get { return y2; } }
        public int Taste { get { return taste; } }
        public OnionSnack(int x1, int y1, int x2, int y2, int taste)
        {
            this.x1 = x1;
            this.y1 = y1;
            this.x2 = x2;
            this.y2 = y2;
            this.taste = taste;
        }
    }
}
